package mine.code.day.year2021.month08;

import org.junit.Test;

/**
 * 给你一个大小为 m x n 的网格和一个球。球的起始坐标为 [startRow, startColumn] 。你可以将球移到在四个方向上相邻的单元格内（可以穿过网格边界到达网格之外）。你 最多 可以移动 maxMove 次球。
 * <p>
 * 给你五个整数 m、n、maxMove、startRow 以及 startColumn ，找出并返回可以将球移出边界的路径数量。因为答案可能非常大，返回对 10^9 + 7 取余 后的结果。
 * <p>
 * 示例 1：
 * <p>
 * 输入：m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0
 * 输出：6
 * <p>
 * 输入：m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1
 * 输出：12
 *
 * @author caijinnan
 */
public class Day15_出界的路径数 {

    @Test
    public void run() {
//        int m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0;
//        int m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1;
//        System.out.println(findPaths(m, n, maxMove, startRow, startColumn));
        //36 5 50 15 3
        int m = 36, n = 5, maxMove = 50, startRow = 15, startColumn = 3;
        System.out.println(findPaths(m, n, maxMove, startRow, startColumn));
        System.out.println(findPathsTest(m, n, maxMove, startRow, startColumn));
    }

    int mod = 1000000007;

    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        // dp[k][x][y] = dp[k-1][x-1][y] + dp[k-1][x+1][y] + dp[k-1][x][y-1] +dp[k-1][x][y+1]
        // sum = dp[0..k-1][m+1][0..n+1]+dp[0..k-1][0..m+1][n+1]+dp[0..k-1][0][0..n+1]+dp[0..k-1][0..m+1][0]
        int[][] around = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        int[][][] dp = new int[maxMove + 1][m + 2][n + 2];
        dp[0][startRow + 1][startColumn + 1] = 1;
        for (int moveNum = 0; moveNum < maxMove; moveNum++) {
            for (int x = 1; x < m + 1; x++) {
                for (int y = 1; y < n + 1; y++) {
                    int num = dp[moveNum][x][y];
                    for (int[] coordinate : around) {
                        int x1 = x + coordinate[0];
                        int y1 = y + coordinate[1];
                        dp[moveNum + 1][x1][y1] = (dp[moveNum + 1][x1][y1] + num) % mod;
                    }
                }
            }
        }
        int sum = 0;
        for (int[][] temp : dp) {
            for (int i = 0; i < m + 2; i++) {
                sum = (sum + (temp[i][0] + temp[i][n + 1])%mod) % mod;
            }
            for (int i = 0; i < n + 2; i++) {
                sum = (sum + (temp[0][i] + temp[m + 1][i])%mod) % mod;
            }
        }
        return sum;
    }


    public int findPathsTest(int m, int n, int maxMove, int startRow, int startColumn) {
        final int MOD = 1000000007;
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int outCounts = 0;
        int[][][] dp = new int[maxMove + 1][m][n];
        dp[0][startRow][startColumn] = 1;
        for (int i = 0; i < maxMove; i++) {
            for (int j = 0; j < m; j++) {
                for (int k = 0; k < n; k++) {
                    int count = dp[i][j][k];
                    for (int[] direction : directions) {
                        int j1 = j + direction[0], k1 = k + direction[1];
                        if (j1 >= 0 && j1 < m && k1 >= 0 && k1 < n) {
                            dp[i + 1][j1][k1] = (dp[i + 1][j1][k1] + count) % MOD;
                        } else {
                            outCounts = (outCounts + count) % MOD;
                        }
                    }
                }
            }
        }
        return outCounts;
    }
}
